package com.gitee.feizns.explore.data_structure.graph;

import com.gitee.feizns.explore.data_structure.graph.utils.Graph;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

/**
 * @author feizns
 * @since 2020/4/29
 */
public class TopologicalSort {

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(0, 1);
        graph.addEdge(0, 3);
        graph.addEdge(1, 2);
        graph.addEdge(3, 2);
        graph.addEdge(2, 4);
        System.out.println(new TopologicalSort(graph).result());
    }

    private Graph graph;

    private boolean hasCycle;

    private List ret;

    public TopologicalSort(Graph graph) {
        this.graph = graph;
        Set nodes = graph.nodes();
        for (Object node : nodes) {
            Set adj = graph.adj(node);
            for (Object o : adj) {
                Integer v = IN_DEGREE.get(o);
                if ( v == null ) v = 0;
                IN_DEGREE.put(o, v + 1);
            }
        }

        ret = new LinkedList();
        Queue queue = new LinkedList();
        for (Object node : nodes) {
            if ( inDegree(node) == 0 )
                queue.add(node);
        }

        while ( !queue.isEmpty() ) {
            Object curt = queue.remove();
            ret.add(curt);
            Set adj = graph.adj(curt);
            for (Object o : adj) {
                int in = inDegree(o);
                IN_DEGREE.put(o, in - 1);
                if ( in == 1 )
                    queue.add(o);
            }
        }

        if ( ret.size() != nodes.size() ) {
            hasCycle = true;
        }
    }

    Map<Object, Integer> IN_DEGREE = new HashMap<>();

    public int inDegree(Object k) {
        return IN_DEGREE.getOrDefault(k, 0);
    }

    public int outDegree(Object k) {
        return graph.adj(k).size();
    }

    public List result() {
        return ret;
    }

    public boolean isHasCycle() {
        return hasCycle;
    }

}
